package jm.algorithm.greedy;

import java.util.*;

/**
 * @Description 0-1 背包
 * @date 2022/5/20 15:56
 */
public class Knapsack {
    public static void main(String[] args) {
        // 价值主导
        Article[] values = select((Article a1, Article a2) -> a2.value - a1.value);
        Info art = getArt(values, 150);
        System.out.println(art);

        // 重量主导
        Article[] weights = select((Article a1, Article a2) -> a1.weight - a2.weight);
        Info art1 = getArt(weights, 150);
        System.out.println(art1);

        // 重量主导
        Article[] density = select((Article a1, Article a2) -> Double.compare(a2.valDensity,a1.valDensity));
        Info art2 = getArt(density, 150);
        System.out.println(art2);
    }

    /**
     * 传入比较器选择以什么为主导
     * @param cmp
     */
    static Article[] select(Comparator<Article> cmp){
        Article[] articles = new Article[]{
                new Article(35, 10), new Article(30, 40),
                new Article(60, 30), new Article(50, 50),
                new Article(40, 35), new Article(10, 40),
                new Article(25, 30)
        };
        Arrays.sort(articles,cmp);
        return articles;
    }

    static Info getArt(Article[] articles, int capacity){
        List<Article> selectArticles = new LinkedList<>();
        int weight = 0;
        int value = 0;
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            int newWeight = weight + articles[i].weight;
            if (newWeight <= capacity){
                weight = newWeight;
                value += articles[i].value;
                selectArticles.add(articles[i]);
            }
        }
        return new Info(selectArticles,weight,value);
    }

    private static class Article{
        int weight;
        int value;
        double valDensity;

        public Article(int weight, int value) {
            this.weight = weight;
            this.value = value;
            this.valDensity = value * 1.0 / weight;
        }

        @Override
        public String toString() {
            return "Article{" +
                    "weight=" + weight +
                    ", value=" + value +
                    ", valDensity=" + valDensity +
                    '}';
        }
    }

    private static class Info{
        int weight = 0;
        int value = 0;
        List<Article> articles;


        public Info(List<Article> articles, int weight, int value) {
            this.articles = articles;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "weight=" + weight +
                    ", value=" + value +
                    ", articles=" + articles +
                    '}';
        }
    }
}
